package j2024.j202412;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class j1216 {
    /**
     * 206. 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode newhead = reverseList(head.next);
        //(i+1)结点的下一个为i
        head.next.next = head;
        head.next = null;
        return newhead;
    }

    /**
     * 234. 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为
     * 回文链表
     * 。如果是，返回 true ；否则，返回 false 。
     */
    public boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        ListNode front = half(head);
        ListNode back = reverseList(front);
        ListNode p1 = head;
        ListNode p2 = back;
        boolean ret = true;
        while(ret && p2!=null){
            if(p1.val!=p2.val){
                ret = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        front.next = reverseList(back);
        return ret;
    }
    public ListNode half(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    ListNode prehead;
    public boolean frontAndBack(ListNode curhead) {
        if(curhead!=null){
            if(!frontAndBack(curhead.next)) return false;
            if(prehead.val!=curhead.val) return false;
            prehead=prehead.next;

        }
        return true;
    }
    public boolean isPalindrome1(ListNode head) {
        prehead = head;
        return frontAndBack(head);
    }

    /**
     * 239. 滑动窗口最大值
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
     * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *
     * 返回 滑动窗口中的最大值 。
     *
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            return b[0]!=a[0]?b[0]-a[0]:b[1]-a[1];
        });
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i],i});
        }
        int[] tmp = new int[n-k+1];
        tmp[0] = pq.peek()[0];
        for (int i = k; i < n; i++) {
            pq.offer(new int[]{nums[i],i});
            while(pq.peek()[1]<=i-k){
                pq.poll();
            }
            tmp[i-k+1] = pq.peek()[0];
        }
        return tmp;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] ret = new int[n-k+1];
        for (int i = 0; i < k; i++) {
            while(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        ret[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; i++) {
            while(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            while(deque.peekFirst()<=i-k){
                deque.pollFirst();
            }
            ret[i-k+1] = nums[deque.peekFirst()];
        }
        return ret;
    }
}
